// ******************************基数排序********************************************
/**
 * 1. 第一次分桶原则，将个位数一样的元素分到同一个桶中
 * 2. 第二次分桶原则，将十位数一样的元素分到同一个桶中
 * 3. ...一直到最高位分桶，若元素位数不一，则空缺的高位补0
 */

function radixSort(arr) {
  //寻找最大值
  let max = Number.MIN_VALUE
  for(let i = 0; i <= arr.length-1; i++) {
      if(arr[i] > max) {
          max = arr[i]
      }
  }
  //利用字符串长度完成最大值位数计算
  let sizeOfMax = (max +"").length;
  //准备10个桶（10个桶集合为二维数组）,因为每一位数字都是0-9
  let bucketArr = new Array(10)
  for(let i = 0; i <= bucketArr.length-1; i++) {
      bucketArr[i] = new Array(arr.length).fill(0)
  }
  //桶计数数组
  let countArr = new Array(10).fill(0)
  //开始循环，个位、十位、百位……
  for(let turn = 0; turn <= sizeOfMax-1; turn++) {
      //按哪位排序由turn决定 0：个位、1：十位、2：百位 ……
      //入桶收集arr
      for(let i = 0; i <= arr.length-1; i++) {
          //pow(10, turn) = 10^turn
          let bucketIndex = Math.floor(arr[i] / Math.pow(10, turn)) % 10
          bucketArr[bucketIndex][countArr[bucketIndex]] = arr[i]
          countArr[bucketIndex]++
      }
      //出桶覆盖arr
      let step = 0
      for(let i = 0; i<= countArr.length-1; i++) {
          if(countArr[i] != 0) {
              for(let j = 0; j <= countArr[i]-1; j++) {
                  arr[step] = bucketArr[i][j]
                  step++
              }
              //计数数组复位
              countArr[i] = 0
          } 
      }
  }

}

//测试用例
let arr = [76,2,102,7,367,45,42,34,897,7,508]
radixSort(arr)
console.log(arr);